package graph

/*

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
线性表可以没有元素，称为空表；树中可以没有节点，称为空树；
但是，在图中不允许没有顶点(有穷非空性)。
线性表中的各元素是线性关系，树中的各元素是层次关系，
而图中各顶点的关系是用边来表示(边集可以为空)。
------
著作权归@pdai所有
原文链接：https://pdai.tech/md/algorithm/alg-basic-graph.html
*/

/*

顶点的度
顶点Vi的度(Degree)是指在图中与Vi相关联的边的条数。对于有向图来说，有入度(In-degree)和出度(Out-degree)之分，有向图顶点的度等于该顶点的入度和出度之和。
邻接
若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接(Adjacent)；
路径
在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径(Path)
连通
若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通(Connected)的。
权(Weight)
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)
*/
/*
无向图
如果图中任意两个顶点之间的边都是无向边(简而言之就是没有方向的边)，则称该图为无向图(Undirected graphs)。
无向图中的边使用小括号“()”表示; 比如 (V1,V2)

有向图
如果图中任意两个顶点之间的边都是有向边(简而言之就是有方向的边)，则称该图为有向图(Directed graphs)。
有向图中的边使用尖括号“<>”表示; 比如/<V1,V2>

完全图
无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
(含有n个顶点的无向完全图有(n×(n-1))/2条边)`
有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。(含有n个顶点的有向完全图有n×(n-1)条边)
*/
/*
图的存储结构
邻接矩阵表示法
一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
无向图：二维数组 住对角线对称
有向图：二维数组 不对称

邻接表表示法
邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。
如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

无向图来说，使用邻接表进行存储也会出现数据冗余的现象
若是有向图，邻接表结构是类似的，但要注意的是有向图由于有方向的。因此，有向图的邻接表分为出边表和入边表(又称逆邻接表

带权图
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可
*/
